Algorithmique - NSI
Algorithme glouton
Exercice 1 : Algorithme glouton et rendu de monnaie
Une caisse dispose des pièces et des billets suivants : 100;75;30;2;1.
On a autant de pièces et de billets que nécessaire.
Lors d'un achat, un caissier doit rendre 78 € à un client.
En utilisant l'algorithme glouton, compléter le tableau ci-dessous, qui répertorie les pièces et billets rendus par le caissier pour que le nombre d'éléments soit minimum :
Exercice 2 : Algorithme glouton et problème du sac à dos
- - La somme des poids des objets sélectionnés soit inférieure à 34 kg.
- - La somme des valeurs des objets sélectionnés soit la plus grande possible.
Exercice 3 : Algorithme glouton et rendu de monnaie
Une caisse dispose des pièces et des billets suivants : 40;20;10;5;1.
On a autant de pièces et de billets que nécessaire.
Lors d'un achat, un caissier doit rendre 224 € à un client.
En utilisant l'algorithme glouton, compléter le tableau ci-dessous, qui répertorie les pièces et billets rendus par le caissier pour que le nombre d'éléments soit minimum :
Exercice 4 : Algorithme glouton et problème du sac à dos
- - La somme des poids des objets sélectionnés soit inférieure à 4 kg.
- - La somme des valeurs des objets sélectionnés soit la plus grande possible.
Exercice 5 : Algorithme glouton et rendu de monnaie
Une caisse dispose des pièces et des billets suivants : 25;20;10;2;1.
On a autant de pièces et de billets que nécessaire.
Lors d'un achat, un caissier doit rendre 72 € à un client.
En utilisant l'algorithme glouton, compléter le tableau ci-dessous, qui répertorie les pièces et billets rendus par le caissier pour que le nombre d'éléments soit minimum :